CopyOnWriteArrayList 源码分析

CopyOnWriteArrayList 线程安全的核心在于其采用了写时复制（Copy-On-Write）的策略，从 CopyOnWriteArrayList 的名字就能看出了。

Note

写入时复制（英语：Copy-on-write，简称 COW）是一种计算机程序设计领域的优化策略。其核心思想是，如果有多个调用者（callers）同时请求相同资源（如内存或磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者试图修改资源的内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的。此作法主要的优点是如果调用者没有修改该资源，就不会有副本（private copy）被创建，因此多个调用者只是读取操作时可以共享同一份资源。

写时复制机制非常适合读多写少的并发场景，能够极大地提高系统的并发性能。

缺点：

内存占用：每次写操作都需要复制一份原始数据，会占用额外的内存空间，在数据量比较大的情况下，可能会导致内存资源不足。
写操作开销：每一次写操作都需要复制一份原始数据，然后再进行修改和替换，所以写操作的开销相对较大，在写入比较频繁的场景下，性能可能会受到影响。
数据一致性问题：修改操作不会立即反映到最终结果中，还需要等待复制完成，这可能会导致一定的数据一致性问题。

插入元素

add(E e)：在 CopyOnWriteArrayList 的尾部插入元素。O(n)
add(int index, E element)：在 CopyOnWriteArrayList 的指定位置插入元素。O(n)
addIfAbsent(E e)：如果指定元素不存在，那么添加该元素。如果成功添加元素则返回 true。O(n)

对于 addAllIfAbsent 方法而言，我觉得是 O(n*m)，所以这里的时间复杂度都很高，算法题不用

// 插入元素到 CopyOnWriteArrayList 的尾部
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    // 加锁
    lock.lock();
    try {
        // 获取原来的数组
        Object[] elements = getArray();
        // 原来数组的长度
        int len = elements.length;
        // 创建一个长度+1的新数组，并将原来数组的元素复制给新数组 ->O(n)
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 元素放在新数组末尾
        newElements[len] = e;
        // array指向新数组
        setArray(newElements);
        return true;
    } finally {
        // 解锁
        lock.unlock();
    }
}

每次写操作都需要通过 Arrays.copyOf 复制底层数组，时间复杂度是 O(n) 的，且会占用额外的内存空间。因此，CopyOnWriteArrayList 适用于读多写少的场景，在写操作不频繁且内存资源充足的情况下，可以提升系统的性能表现。

读取元素

// 底层数组，只能通过getArray和setArray方法访问
private transient volatile Object[] array;

public E get(int index) {
    return get(getArray(), index);
}

final Object[] getArray() {
    return array;
}

private E get(Object[] a, int index) {
    return (E) a[index];
}

get 方法是弱一致性的，在某些情况下可能读到旧的元素值。

这个过程并没有加锁，所以在并发环境下可能出现如下情况：

线程 1 调用 get(int index)方法获取值，内部通过 getArray()方法获取到了 array 属性值；
线程 2 调用 CopyOnWriteArrayList 的 add、set、remove 等修改方法时，内部通过 setArray 方法修改了 array 属性的值；
线程 1 还是从旧的 array 数组中取值。

CopyOnWriteArrayList 没有像 ArrayList 一样预留空间，直接 size() 知道长度，而不是 length